Міністерство освіти та науки України
Національний університет «Львівська політехніка»
/
ЗВІТ
З лабораторної роботи №5
З дисципліни: «Алгоритми та методи обчислень»
На тему: «Використання способів зменшення часової складності алгоритму на прикладі алгоритму швидкого перетворення Фурье»
Мета роботи: ознайомитись з алгоритмом ШПФ та одночасним використанням різних методів зменшення часової складності при побудові алгоритму.
МЕТОДИЧНІ МАТЕРІАЛИ
В сучасних каналах зв'зку широко використовуються пристрої цифрового оброблення сигналів. Ці пристрої реалізують той чи інший алгоритм цифрового оброблення. Прикладами таких алгоритмів є аналіз і синтез цифрових фільтрів, спектральний аналіз сигналів, кепстральній аналіз, модуляція сигналу, демодуляція, перенос та інверсія спектру та інші.
Цифровий фільтр являє собою пристрій, який перетворює вхідний сигнал. Вид перетворення повністю визначається характеристиками фільтру. Фільтр призначений для частотної селекції сигналів. Він пропускає з малим ослаьленням корисні частотні складові (гармоніки) спектра сигналу і значно послаблює гармоніки, присутність яких у спектрі вихідного сигналу є небажаною.
Існують різні способи реалізації фільтрів зі скінченими імпульсними характеристиками. Серед них - пряма згортка і шидка згортка.
Пряма згортка
Нехай x(nT) і h(nT) – дві періодичні послідовності з періодами по N відліків.
Періодичною ( циклічною ) згорткою таких послідовностей називається послідовність y(nT), яка визначається співвідношенням:
,
Послідовність y(nT) також є періодичною з періодом N відліків, тому достатньо обчислити її на одному періоді, наприклад при n = 0, 1, … ,N-1. Це співвідношення справедливе і для скінчених послідовностей x(nT) і h(nT) (n = 0, 1, … ,N-1), якщо розглядати їх як один період відповідних їм періодичним послідовностям. Періодична згортка скінчених послідовностей також буде скінченою.[11]
Якщо ,то кількість операцій множення додавання в кожному рядку дорівнює N, кількість рядків теж дорівнює N. Тому загальна кількість множень додавань (часова складність) дорівнює N2.
Швидка згортка.
Одним із варіантів швидкої згортки може бути обчислення згорки за допомогою операції ДПФ. Для цього необхідно виконати наступні дії:
Обчислення ДПФ послідовності x(nT) :
, k = 0, 1, … ,N-1
;
Обчислення ДПФ послідовності h(nT) :
, k = 0, 1, … ,N-1
Перемноження коефіціентів отриманих ДПФ :
Y(k) = X(k) H(k), k = 0, 1, … ,N-1
Обчислення ЗДПФ послідовності Y(k) :
, n = 0, 1, … ,N-1
Послідовність y(nT) і є згортка.
Звідки видно, що операція згортки в часовій області еквівалентна множенню в частотній області. Це співвідношення має велике значення через те, що дозволяють виконувати лінійне оброблення сигналів і моделювати лінійні системи. Стосовно до цих задач x(nT) та y(nT) розглядаються як вхідний та віхідний сигнали системи, а h(nT) – як її імпульсна характеристика.
Таким чином, згортку можна виконувати або безпосередньо за співвідношенням (1), або непрямим методом, використовуючи ДПФ для перетворення періодичних функцій часу в частотну область. В останньому випадку для отримання Y(k) при заданих h(nT) i x(nT) потрібно обчислити і перемножити відповідні перетворення H(k) i X(k). Після чого Y(k) перетворюється за допомогою зворотнього ШПФ у вихідний сигнал системи y(nT).
На перший погляд обчислення згортки в частотній області здається більш тривалою операцією в порівнянні з прямим методом. Насправді ж непрямий метод може бути швидшим. Причина цього полягає в існуванні ефективного методу обчислення ДПФ та ЗДПФ, відомого як "Швидке перетворення Фур'е".
Кепстральний аналіз дозволяє розділяти сигнал і заваду, які взаємодіють через згортку Для розділення у загальному випадку використовується лінійний фільтр. Для того, щоб його застосувати, необхідно перетворити сигнал і заваду, які взаємодіють через згортку у їх суму . Це перетворення наступне:
→ШПФ→ фільтр →→ЗШПФ→.
Цей вираз називається кепстром. Тепер за допомогою лінійно...
